\documentclass[journal]{IEEEtran}
% If the IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it:
% \documentclass[journal]{../sty/IEEEtran}


% some very useful LaTeX packages include:

\usepackage{cite}      % Written by Donald Arseneau
                        % V1.6 and later of IEEEtran pre-defines the format
                        % of the cite.sty package \cite{} output to follow
                        % that of IEEE. Loading the cite package will
                        % result in citation numbers being automatically
                        % sorted and properly "ranged". i.e.,
                        % [1], [9], [2], [7], [5], [6]
                        % (without using cite.sty)
                        % will become:
                        % [1], [2], [5]--[7], [9] (using cite.sty)
                        % cite.sty's \cite will automatically add leading
                        % space, if needed. Use cite.sty's noadjust option
                        % (cite.sty V3.8 and later) if you want to turn this
                        % off. cite.sty is already installed on most LaTeX
                        % systems. The latest version can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/cite/

%\usepackage{graphicx}  % Written by David Carlisle and Sebastian Rahtz
                        % Required if you want graphics, photos, etc.
                        % graphicx.sty is already installed on most LaTeX
                        % systems. The latest version and documentation can
                        % be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/required/graphics/
                        % Another good source of documentation is "Using
                        % Imported Graphics in LaTeX2e" by Keith Reckdahl
                        % which can be found as esplatex.ps and epslatex.pdf
                        % at: http://www.ctan.org/tex-archive/info/
% NOTE: for dual use with latex and pdflatex, instead load graphicx like:
%\ifx\pdfoutput\undefined
%\usepackage{graphicx}
%\else
%\usepackage[pdftex]{graphicx}
%\fi

% However, be warned that pdflatex will require graphics to be in PDF
% (not EPS) format and will preclude the use of PostScript based LaTeX
% packages such as psfrag.sty and pstricks.sty. IEEE conferences typically
% allow PDF graphics (and hence pdfLaTeX). However, IEEE journals do not
% (yet) allow image formats other than EPS or TIFF. Therefore, authors of
% journal papers should use traditional LaTeX with EPS graphics.
%
% The path(s) to the graphics files can also be declared: e.g.,
% \graphicspath{{../eps/}{../ps/}}
% if the graphics files are not located in the same directory as the
% .tex file. This can be done in each branch of the conditional above
% (after graphicx is loaded) to handle the EPS and PDF cases separately.
% In this way, full path information will not have to be specified in
% each \includegraphics command.
%
% Note that, when switching from latex to pdflatex and vice-versa, the new
% compiler will have to be run twice to clear some warnings.


%\usepackage{psfrag}    % Written by Craig Barratt, Michael C. Grant,
                        % and David Carlisle
                        % This package allows you to substitute LaTeX
                        % commands for text in imported EPS graphic files.
                        % In this way, LaTeX symbols can be placed into
                        % graphics that have been generated by other
                        % applications. You must use latex->dvips->ps2pdf
                        % workflow (not direct pdf output from pdflatex) if
                        % you wish to use this capability because it works
                        % via some PostScript tricks. Alternatively, the
                        % graphics could be processed as separate files via
                        % psfrag and dvips, then converted to PDF for
                        % inclusion in the main file which uses pdflatex.
                        % Docs are in "The PSfrag System" by Michael C. Grant
                        % and David Carlisle. There is also some information 
                        % about using psfrag in "Using Imported Graphics in
                        % LaTeX2e" by Keith Reckdahl which documents the
                        % graphicx package (see above). The psfrag package
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/psfrag/

%\usepackage{subfigure} % Written by Steven Douglas Cochran
                        % This package makes it easy to put subfigures
                        % in your figures. i.e., "figure 1a and 1b"
                        % Docs are in "Using Imported Graphics in LaTeX2e"
                        % by Keith Reckdahl which also documents the graphicx
                        % package (see above). subfigure.sty is already
                        % installed on most LaTeX systems. The latest version
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/subfigure/

%\usepackage{url}       % Written by Donald Arseneau
                        % Provides better support for handling and breaking
                        % URLs. url.sty is already installed on most LaTeX
                        % systems. The latest version can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/other/misc/
                        % Read the url.sty source comments for usage information.

%\usepackage{stfloats}  % Written by Sigitas Tolusis
                        % Gives LaTeX2e the ability to do double column
                        % floats at the bottom of the page as well as the top.
                        % (e.g., "\begin{figure*}[!b]" is not normally
                        % possible in LaTeX2e). This is an invasive package
                        % which rewrites many portions of the LaTeX2e output
                        % routines. It may not work with other packages that
                        % modify the LaTeX2e output routine and/or with other
                        % versions of LaTeX. The latest version and
                        % documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/sttools/
                        % Documentation is contained in the stfloats.sty
                        % comments as well as in the presfull.pdf file.
                        % Do not use the stfloats baselinefloat ability as
                        % IEEE does not allow \baselineskip to stretch.
                        % Authors submitting work to the IEEE should note
                        % that IEEE rarely uses double column equations and
                        % that authors should try to avoid such use.
                        % Do not be tempted to use the cuted.sty or
                        % midfloat.sty package (by the same author) as IEEE
                        % does not format its papers in such ways.

%\usepackage{amsmath}   % From the American Mathematical Society
                        % A popular package that provides many helpful commands
                        % for dealing with mathematics. Note that the AMSmath
                        % package sets \interdisplaylinepenalty to 10000 thus
                        % preventing page breaks from occurring within multiline
                        % equations. Use:
%\interdisplaylinepenalty=2500
                        % after loading amsmath to restore such page breaks
                        % as IEEEtran.cls normally does. amsmath.sty is already
                        % installed on most LaTeX systems. The latest version
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/



% Other popular packages for formatting tables and equations include:

%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty which improves the
% LaTeX2e array and tabular environments to provide better appearances and
% additional user controls. array.sty is already installed on most systems.
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/

% Mark Wooding's extremely powerful MDW tools, especially mdwmath.sty and
% mdwtab.sty which are used to format equations and tables, respectively.
% The MDWtools set is already installed on most LaTeX systems. The lastest
% version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/mdwtools/


% V1.6 of IEEEtran contains the IEEEeqnarray family of commands that can
% be used to generate multiline equations as well as matrices, tables, etc.


% Also of notable interest:

% Scott Pakin's eqparbox package for creating (automatically sized) equal
% width boxes. Available:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/eqparbox/



% Notes on hyperref:
% IEEEtran.cls attempts to be compliant with the hyperref package, written
% by Heiko Oberdiek and Sebastian Rahtz, which provides hyperlinks within
% a document as well as an index for PDF files (produced via pdflatex).
% However, it is a tad difficult to properly interface LaTeX classes and
% packages with this (necessarily) complex and invasive package. It is
% recommended that hyperref not be used for work that is to be submitted
% to the IEEE. Users who wish to use hyperref *must* ensure that their
% hyperref version is 6.72u or later *and* IEEEtran.cls is version 1.6b
% or later. The latest version of hyperref can be obtained at:
%
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/hyperref/
%
% Also, be aware that cite.sty (as of version 3.9, 11/2001) and hyperref.sty
% (as of version 6.72t, 2002/07/25) do not work optimally together.
% To mediate the differences between these two packages, IEEEtran.cls, as
% of v1.6b, predefines a command that fools hyperref into thinking that
% the natbib package is being used - causing it not to modify the existing
% citation commands, and allowing cite.sty to operate as normal. However,
% as a result, citation numbers will not be hyperlinked. Another side effect
% of this approach is that the natbib.sty package will not properly load
% under IEEEtran.cls. However, current versions of natbib are not capable
% of compressing and sorting citation numbers in IEEE's style - so this
% should not be an issue. If, for some strange reason, the user wants to
% load natbib.sty under IEEEtran.cls, the following code must be placed
% before natbib.sty can be loaded:
%
% \makeatletter
% \let\NAT@parse\undefined
% \makeatother
%
% Hyperref should be loaded differently depending on whether pdflatex
% or traditional latex is being used:
%
%\ifx\pdfoutput\undefined
%\usepackage[hypertex]{hyperref}
%\else
%\usepackage[pdftex,hypertexnames=false]{hyperref}
%\fi
%
% Pdflatex produces superior hyperref results and is the recommended
% compiler for such use.



% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
\title{A Scalable and Hierarchical Tagging System}
\author{Bindu~Madhav~Krishna~Miriyala, \today}
\markboth{A Scalable and Hierarchical Tagging System}

\maketitle


\begin{abstract}
Although awareness for the need of non-orthodox filesystems is continuously increasing in the computing world, current efforts trying to tweak with tags or search engines are unlikely to succeed. Current efforts fail to discover that the size of the local filesystems are growing rapidly, but the amount of information that is accessed within a context of time is likely to be at the same level. The information access patterns has changed enormously over the last few years, forcing the filesystems to evolve at the same pace. But in reality, the file-systems are at the same level as in 1990's, though improved a lot in stability, durability but are at the same level in providing the users with a better way to access the information. This paper identifies the need for the change in the information access patterns and the new features that need to be integrated in the filesystems, ultimately leading to the next generation file-system that can handle access to any data being accessed from the computer and provide a systematic access as required by the user.
\end{abstract}

\begin{keywords}
Algorithms, Filesystems, Tagging Systems, Paper.
\end{keywords}

\tableofcontents

\section{Introduction}
\PARstart{T}{he} concept of Tag based filesystems is the motivation for the current work. We shall give an idea on the issues with the traditional filesystems and how various conceptual and commericial systems tried to solve the problems but still lag far behind to be fully functional. Traditional file systems both in Unix and Windows, have only one way of accessing the files, which is a hierarchical file organization into files and folders. Typical filesystem size can be in the range of millions in the present world of increasing information outblast. 
	Any file can be accessed by a unique hierarchical path from the top folder 
	Files are organized into directories, subdirectories, and filenames with extensions.

Here, we see that the file-systems are developed keeping in view of only the traditional files locally available on the systems. The generation is slowly moving into the web-maniac world, where most of the information is accessed from the internet and most of the information is retrieved as files/webpages from the internet. The traditional single method of organizing data leads to considerable inefficiencies in accessing files locally as well as from the internet. Many search based application tried to fill the gaps in the traditional way of access but could only solve the problem of the accessing unknown information and seem to fail to organize well the data very frequently accesed by the users.

To improve the search, current file systems uses a variety of techniques. Microsoft Vista uses tags but only associated with specific file types. Mac OS uses a spotlight feature to add keywords to files. Embedding keywords into files is the most common technique for providing a search facility to the user. In each of these operating systems, keywords are indexed and a database is used to answer user queries. To summarize, current file systems require update to provide a more flexible method to organize data. Most of the times, the information/file being accessed once has a chance of being accessed multiple times, but search engines never perform the task of enabling easier access to the mostly used information/files in a systematic way.


We start off by taking the multi hierarchy user defined system- called the Abstract File System, as the base system and extending it to next level of abstraction where any kind offile can be handled by the system, to make the view for the user more presentable and attractive. In this system the user has the option to organize the data in multiple hierarchical forms which would aid considerably in searching and organizing search results, i.e., files, in a well structured fashion as needed by the user.

As an example consider the following structure of files (Figure1)
Pictures/2006/dad
Pictures/2005/dad
Pictures/2006/mom
Pictures/2005/mom
Pictures/2006/baby
Pictures/2005/baby


Suppose we wanted to access all files which involve dad, i.e.
Pictures/dad

The number of files may be substantial and so it is desired that these may be classified further as (Figure 2)
Pictures/dad/2005
Pictures/dad/2006
Pictures/dad/baby
Pictures/dad/mom

While this is partly accomplished by incorporating search keywords generally for specific kind of files, but none of the commercial systems have the possibility of showing an orthogonal view (Say, all the files related to this project like sources, documentation, emails, references etc). While this can be partly accomplished by related links in other files are using keywords, but can never view under the same hood. Hence we use the notion of structured keywords and abstract directories so that files can be organized in any user specified hierarchies. Since the concept of abstract directories can help in linking any kind of information, this can help us organize any kind of data like reference urls, online files to be hooked under the same hood, easing the problem of accessing the information from different tools and methods.

We extend this methodology described in the Abstract File System paper with an ultimate goal of the next generation file system, that has uniform and efficient way of accessing local/remote files. In this system the user can organize the data in multiple hierarchical forms which would aid considerably in searching and organizing search results, i.e., files, in a structured fashion. 

\subsection{Prior Work and Motivation}
\subsubsection{TagFS}
An effort was made to extend the file system to include tags in TagFS- Tag semantics for Hierarchical File Systems [TagFS]. In this approach, files are annotated using Resource Description Framework (RDF)[W3RDF] and the notion of traditional folders is interpreted as a view of the RDF graph. A query of the form /a/b/c return the view (RDF graph) of all data tagged with “a” and “b” and “c” . The files so tagged can be listed by a list command (LS). A mapping from traditional file operations to queries on the TagFS system is also provided. Importantly, the notion of hierarchy is removed from this file system. We believe that hierarchy is important and is preserved in our approach. Implementation details and experimental results on TagFS are not provided.


\subsubsection{LogicalFS}
Another file system proposed is the Logical File System (LFS) [LFS]. This generalizes the previous results in that the path (PWD) is interpreted as a Boolean formula and the LS command returns all files which satisfy the Boolean formula. Each file has a property name and queries use this property name (tag). While the authors introduce the notion of hierarchy in properties, the file system is not hierarchical, and the path a/b/c results in the same set of files as b/c/a. The authors propose a generalization of the Uunix inode structure to store information about files having the same property name. Experimental results are provided but are not encouraging. In comparison to Linux/Unix file systems, the time to copy files increases 5 folds on some benchmarks.

\subsubsection{LinkFS}
In Linked File Systems (LFS) files are provided with meta-data in the form of key-value pairs on files and links between files [LiFS]. The links have attributes and are used for linking together files. This entire graph structure is stored in a database and scanned to produce all files linked via the same attribute. A search for files linked via an attribute is organized via a BFS on this graph. Again this approach does not address hierarchical organization into virtual directories and does not appear efficient when files are deleted.


\subsubsection{SemFS}
In SemFS [SFS], file attributes are obtained using transducers. An attribute is a field-value pair where the field describes a property, and the value, a value of that property. A query is specified by attributes and the result, stored in a virtual directory, is a set of files and/or directories that contain the entities with the particular attribute value. The virtual directory contains symbolic links to actual files/directories. This system does not allow for hierarchical tag structures. The implementation is via B-Trees and does not allow for immediate updates to the index. Since it is a database oriented implementation, the database updates are batched, time-consuming, and not available immediately upon changes to the file system. Sedar is a similar peer-to-peer file system which facilitates semantic searching [SEDAR]. A query will return files semantically similar to the query file. Semantic hashing is used. The output is a virtual folder similar to the one in SemFS.

\subsubsection{InvFS}
In the Inversion File System [IFS], again, a database approach is used to store both file data and metadata. This system relies on a database to ensure transaction protection. Files can be queried by both file name and metadata. Another approach to creating different views of file systems is one that allows for unification of file systems [UFS]. However these systems do not address metadata.

\subsection{Commercial Systems}
\subsubsection{Microsoft's WinFS}
Microsoft’s WinFS uses a database for storing the metadata and NTFS for file handling [WinFS] WinFS stores data in virtual locations called stores. A WinFS store is a common repository where every application will store its data, along with its metadata, relationships and information on how to interpret the data. In this way, WinFS does away with the folder hierarchy, and allows searching across the entire repository of data.

WinFS store is actually a relational store, where applications can store their structured as well as unstructured data. Based on the meta-data, type of data, and also the relationships of the data with other data as will be specified by the application or the user, WinFS will assign a relational structure to the data. By using the relationships, WinFS aggregates related data. WinFS stores are exposed as shell objects, similar to Virtual folders, which dynamically generates a list of all items present in the store and presents them in a folder view. The shell object also allows searching information in the data store.

\subsubsection{Apple's Spotlight}
Apple Computer's Spotlight [Spot] indexes the metadata and content and stores them in a database. The system automatically updates its index when a file when is created, saved, moved copied or deleted, thus search results are always up-to-date. A simple command line tool to query the index is provided.

\subsubsection{Web-based Systems}
Information about Web-based Systems like Bookmarks, Delicious, Gmail.

In summary, although prior systems exist, nothing in the prior art supports multiple, simultaneous, searchable, hierarchical tagging schemes.



\section{A Scalable and Hierarchical Tagging System (SHTS)}
\subsection{Concept}

SHTS provides the users the capability to describe any information accessed by the users with user-defined words called hierarchical tags and allow them to access information in a systematic way. Hierarchical tags can also include the simple keywords which help in search for all information within the specific domain. The tags are of the form.

   a. <tag>
	Tags of this (a) provides a normal search result with all the results in one single abstraction leaving the task for the user to go through the list. 
   b. /<tag1>/<tag2>/….<tagk>.
	Hierarchical tags provide a more structured searching of the information and hence well defined way for users to navigate through the information.

In Example 1, assigning tags

Pictures/dad/2005
Pictures/dad/2006
Pictures/dad/baby
Pictures/dad/mom
Pictures/mom/2005
Pictures/mom/2006

would provide an orthogonal directory structure. A Query for
Pictures/

would provide an abstract folder with the subdirectories
dad/ and mom/

and the search for Pictures/dad would provide an abstract folder with the directories
2005/ 2006/ baby/ mom/

In general a search for <Dir>/ provides all files labeled <Dir>/<file> and all directories , <dir>, of files labeled Dir1/<dir>/*.
Directories may also be tagged with the same methodology.


Abstract Folder operations
The abstract folders allow features for generalized tag modifications. Within a reported abstract folder a user can choose a set of files and add tags to all these files. Tags for a specific file can be reported. Tags common to a chosen set of files can also be reported. Files in an abstract folder can be operated upon in the same way as a regular folder.

Abstract Folders as Hypergraph linked File Structures
A graph theoretic view of this solution introduces the notion of hypergraph linked file structures. The traditional hierarchical structure can be represented as a tree, with the files at each node. A tag is defined as an hyperedge, connecting the nodes corresponding to the files that have been described with the specified tag. That is, given a collection of files stored in a traditional tree folder system, we consider linking files via a hyper-edge. A set of files form a hyper-edge labeled via a tag. A tree node can belong to multiple hyper-edges. We thus get a hypergraph file system which the user can user to cross-index his/her files. Multi-hypergraph edges allowed (Figure 3). The structure of tags, as explained above, can be hierarchical in nature. Thus, a tag can be of the form <dir1>/<dir2>/…./<tag>

Implementing ABFS.

\subsection{Review of various Data-Structures}
\subsubsection{B-Tree}
B-Tree is a multi-way balanced tree comprised of two types of nodes: internal and leaf. Internal nodes are used as actual index or the road-map to the leaf nodes that contain the actual data. A balanced B-Tree is considered to be the most efficient for maintaining the sorted data on disk which can guarantee  worst-case O$\left(log_BN\right)$ for searching N keys with a max fanout of B. In normal case a minimum fanout of B/2 is maintained, hence O$\left(log_{B/2}N\right)$ is  easily achievable. B-Trees have been widely used to manage and retrieve large vocabularies associated with text databases. Linux ReiserFS and Windows NTFS uses B-Trees.

\begin{itemize}
\item Even with large volumes of data, the height of the B-Tree remains very low due to the large fanout factor.
\item All nodes are guaranteed to have a 50\% load factor (70\% on an average case).
\item Unlike a Binary Search tree, B-Tree is a balanced structure with a gauranteed worst-case cost
\item As the data is maintained in sorted order, range queries are easily implemented.
\item Even for large volumes of data the number of disk accesses can be reduced to a huge extent using a large branching factor.
\end{itemize}

\subsubsection{B-Tree Variants}
B*-Tree:
Every leaf with a minimum load of 67\%  here instead of splitting one node, the sibling node is accessed and they are both split into three, depending on the space availability.
Here the space consumption is reduction at the cost of more disk accesses.

Dense Multiway Trees: 
Every leafwith a minimum load of 99\%, where each node searches for the siblings in all directions to store the overflowing data.

M-Trees \& P-Tree: are similar variants that are impractical for disk-based or large files.

\subsubsection{B-Trie}
A disk-resident Trie has the potential to be a competitive alternative mainly for sorted storage of data where strings are used as keys.
This variant of B-Trie uses the concept of Burst-Trie by writing the nodes to disk. Hence similar to the B-Tree this consists of two nodes called as Trie and bucket.

\subsubsection{Burst-Trie}
When a bucket is deemed to full in memory, it is burst into a maximum of $\|A\|$ buckets. Buckets can be of variable size in memory, but when they are written to disk, they are of fixed size. Hence Bursting of a bucket can lead upto $\|A\|$ new buckets which is waste of space and lots of disk-ios can happen in case of bursting and the range queries due to spread of the data in more number of buckets

Records: A record is a string to be stored in the Trie with all the information required along with it like the statistics, other information to be stored with the string.

Containers: A container is like a bucket that is used to store a small set of records maintained in a simple datastructure like BST or linkedlist. It also contains a small header that can be used to store heuristics that can be later used for bursting.

Access Trie: An Access Trie is a trie whose leaves are containers. Each node will have upto $\|A\|$ number of pointers. This is represented as array of n pointers where n is the size of the alphabet.  

Better Approach: Hence, a better approach is required for disk based systems leading to less number of disk i/os and less space when splitting into $\|A\|$ buckets is waste of space and time. In such cases, every bucket is deemed as hybrid or pure, depending on the data it contains that are populated during the split. A hybrid is allowed to contain words with different prefixes. But a pure bucket can contain only words/strings with a common prefix. When a pure bucket is split, it leads to creation of a trie node and two hybrid buckets sharing the strings between them. In case of splitting of hybrid buckets, it leads to two hybrid or hybrid+pure or pure+pure dependin upon the distribution of the strings in that particular bucket.

\subsubsection{HAT-Trie}
Another variant of Burst-Trie, the strings in the buckets are stored as move-to-front hash lists. But this variant has the issue of range query incapability and hence used only in special applications that require only point queries.

\subsubsection{Cache-Oblivious String B-Tree}
A cache-oblivious string B-Tree is theoretically designed to perform well on all levels of memory hierarchy.

\subsection{Implementation}
\subsection{Interfaces and Algorithms}

\section{Proposals for Future Work}
\subsection{Improvement of Data-Structures}
\subsection{Integrating to Desktop Applications}
\subsection{Ultimate Goal - Next Generation Information System}

\pagebreak
\begin{thebibliography}{1}

\bibitem{NAJZ}
Nikolas Askitis and Justin Zobel: \emph{B-tries for disk-based string management}, \copyright Springer-Verlag 2008. [NAJZ]
\bibitem{TAGFS}
Stephan Bloehdorn, Olaf Görlitz, Simon Schenk, Max Völkel: \emph{TagFS -- Tag Semantics for Hierarchical File Systems},  In Proceedings of the 6th International Conference on Knowledge Management (I-KNOW 06), Graz, Austria, September 6-8,2006.



\end{thebibliography}

\end{document}
